package com.structure.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * 合并多个有序的列表，可以参考归并排序
 * 合并思路和双列表一样
 * Created by sucre on 2015/12/1.
 */
public class MergeKListII {
    public ListNode mergeKLists(List<ListNode> lists) {
        if(lists ==null || lists.size() ==0){
            return null;
        }
        while(lists.size() >1){
            List<ListNode> newList = new ArrayList<ListNode>();
            //这里要注意，因为取到了i+1,所以要判断i+1的长度，步长改为i+2
            for(int i=0;i+1<lists.size();i+=2){
                newList.add(mergeTwoLists(lists.get(i),lists.get(i+1)));
            }
            //如果list为奇数，直接将最后一个ListNode放到新的list中，参加下一次循环
            if((lists.size() & 1)==1){
                newList.add(lists.get(lists.size() -1));
            }
            lists = newList;
        }
        return lists.get(0);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个为0的节点，其它节点放到它的next位上
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        //两个不能都存在时进入
        while(l1!=null && l2 !=null){
            //判断当前节点值的大小
            if(l1.val <= l2.val){
                //将大的列表当前节点的值赋给pre.next
                pre.next = l1;
                //这一步很关键，要将当前列表的其它节点顺次前移
                l1 = l1.next;
            }else{
                pre.next = l2;
                l2 = l2.next;
            }
            //这一步很关键，pre.next的地址赋给pre,使得pre始终保持单节点，这样有利于l1或l2节点的值合并到pre上
            pre = pre.next;
        }
        //因为链表是有序的，所以将剩下的内容直接复制到pre.next即可
        if(l1 !=null){
            pre.next = l1;
        }else{
            pre.next =l2;
        }
        return dummy.next;
    }
    public static void main(String[] args){
        System.out.print(3&1);
    }
}
